package com.hanxiaozhang.dichotomic;

/**
 * 〈一句话功能简述〉<br>
 * 〈二分法〉
 *
 * @author hanxinghua
 * @create 2021/9/3
 * @since 1.0.0
 */
public class Dichotomic {

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 8, 10};
        System.out.println(dichotomic4(arr, 8));
    }

    /**
     * 二分算法一
     *
     * @param arr
     * @param number
     * @return
     */
    public static int dichotomic1(int[] arr, int number) {

        int left = 0, right = arr.length - 1, middle = 0;
        while (left < right) {
            middle = (left + right) / 2;
            if (arr[middle] == number) {
                return middle;
            } else if (arr[middle] > number) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return arr[left] == number ? left : -1;
    }


    /**
     * 二分算法二
     *
     * @param arr
     * @param number
     * @return
     */
    public static int dichotomic2(int[] arr, int number) {

        int left = 0, right = arr.length - 1, middle = 0;
        while (left < right) {
            // 避免运算溢出
            middle = left + ((right - left) >> 2);
            if (arr[middle] == number) {
                return middle;
            } else if (arr[middle] > number) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return arr[left] == number ? left : -1;
    }


    /**
     * 二分算法变形
     * 在一个有序数组中，找出>=某个数最左侧的位置
     *
     * @param arr
     * @param number
     * @return
     */
    public static int dichotomic3(int[] arr, int number) {

        int left = 0, right = arr.length - 1, middle = 0, index = -1;
        while (left <= right) {
            // 避免运算溢出
            middle = left + ((right - left) >> 2);
            if (arr[middle] >= number) {
                index = middle;
                // 缩小范围
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return index;
    }


    /**
     * 二分算法变形
     * 在一个有序数组中，找出<=某个数最右侧的位置
     *
     * @param arr
     * @param number
     * @return
     */
    public static int dichotomic4(int[] arr, int number) {

        int left = 0, right = arr.length - 1, middle = 0, index = -1;
        while (left < right) {
            // 避免运算溢出
            middle = left + ((right - left) >> 2);
            if (arr[middle] <= number) {
                index = middle;
                // 缩小范围
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return index;
    }


    /**
     * 二分算法变形
     * 无序一个数组，相邻两个元素不等，找出任意一个局部最小
     *
     * @param arr
     * @return
     */
    public static int dichotomic5(int[] arr) {

        // 极端情况处理：
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 && arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int left = 0, right = arr.length - 2, middle = 0;
        while (left < right) {
            // 避免运算溢出
            middle = left + ((right - left) >> 2);
            if (arr[middle] > arr[middle - 1]) {
                right = middle - 1;
            } else if (arr[middle] > arr[middle + 1]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return left;
    }


}
